This invention relates in general to the fields of supply chain management, and single-enterprise and multi-enterprise planning and scheduling. More particularly, the present invention relates to a computer implemented scheduling system and process that uses an abstract local search technique.
Computer implemented planning and scheduling systems are widely used for factory, enterprise and supply chain planning functions. In general, such systems can model the manufacturing or other environment and provide plans or schedules for producing items to fulfill consumer demand within the constraints of the environment.
The problem of planning or scheduling an environment can be represented as a constrained optimization problem. For example, consider a simple problem of sequencing a set of tasks on a resource in a manufacturing environment. In addition, assume that each task has a deadline, and the objective is to schedule each task so that it ends by the associated deadline. One way to view this problem, for example, is as a search in the space of start times. Under this view, the problem becomes a simple constrained optimization problem in which the variables are the start times, the constraint is that no tasks can overlap, and the objective is to minimize lateness. This type of approach to planning and scheduling problems can provide an efficient framework for producing plans.
An abstract local search (ALS) is an efficient approach for analyzing and resolving planning and scheduling a manufacturing or other environment. An ALS solves combinatorial optimization problems by making local moves in the space of abstract solutions. An abstract solution (for example, a task ordering) is mapped to a concrete solution (for example, a schedule) by a greedy solution builder that, generally, enforces all hard constraints. The concrete solution is then evaluated to determine flaws, usually by measuring soft constraint violations. The flaws in the concrete solution are used to generate modifications (moves) in the abstract solution, that might reduce the flaws in the concrete solution.
In non-analogous contexts, detecting flaws in concrete solutions and using them to drive modifications in abstract solutions has been shown to be effective in several local search applications (for example, GSAT for propositional satisfiability problems. Selman, Kautz, and Cohen, xe2x80x9cLocal Search Strategies for Satisfiability Testingxe2x80x9d, 1993, Vol. 26, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (American Mathematical Society). One article attributes the effectiveness of iterative repair to making use of important information about the current solution to guide the search. Minton, Johnston, Philips, and Laird, xe2x80x9cSolving large-scale constraint satisfaction and scheduling problems using a heuristic repair methodxe2x80x9d, Artificial Intelligence 58:161-205 (1990).
In accordance with the present invention, a computer implemented scheduling system and process are disclosed that use an abstract local search technique.
A technical advantage of the present invention is that the abstract local search technique is useful for solving constrained optimization problems. It is particularly suited to a problem domain where some fast deterministic algorithm can map a set of priorities into a solution that satisfies the hard constraints in the problem.
Although some forms of priorities have previously been used for representing schedules, no general framework to integrate priorities into local search has been proposed. It is presented herein that the basic loop of priorities feeding into a greedy solution builder and an analysis technique that updates the priorities will be applicable to a large class of constrained optimization problems, and will scale to problems of realistic size and complexity.